package com.arron.algorithm.leetcodetop100.回溯;


import java.util.HashMap;
import java.util.Map;

/**
 *  动态规划
 * @see com.arron.algorithm.leetcodetop100.动态规划.背包问题.目标和
 */
public class 目标和 {
    int target;
    int count;

    Map<String,Integer> memMap;

    public int findTargetSumWays(int[] nums, int target) {

        this.target = target;
        memMap = new HashMap<>();
        find(nums, 0, 0);
        return this.target;
    }



    public void find(int[] nums, int start, int sum) {
        if (start == nums.length && sum == this.target) {
            this.count++;
            return;
        }

        if (start > nums.length) {
            return;
        }

        //选择正号
        find(nums, start + 1, sum + nums[start]);

        //选择负号
        find(nums, start + 1, sum - nums[start]);


    }


    /**
     *  使用map进行记忆递归 ，递归函数 参数start,sum时变化值
     * @param nums
     * @param start
     * @param sum
     */
    public int find_plus(int[] nums, int start, int sum) {
        String key = start+"_"+sum;

        if (memMap.containsKey(key)){
           return memMap.get(key);
        }

        if (start == nums.length) {
            if (!memMap.containsKey(key)){
                memMap.put(key,sum == this.target ? 1:0);
            }
            return memMap.get(key);
        }

        if (start > nums.length) {
            return 0;
        }



        //选择正号
        int left = find_plus(nums, start + 1, sum + nums[start]);

        //选择负号
        int right = find_plus(nums, start + 1, sum - nums[start]);

        memMap.put(key,right+left);
        return memMap.get(key);
    }

    public static void main(String[] args) {

        目标和 findTarget = new 目标和();
        int[] nums = {1, 1, 1, 1, 1};
        System.out.println(findTarget.findTargetSumWays(nums, 3));
    }

}
